The present application relates to Peer-to-Peer (P2P) communications, and more particularly to the multicast trees topology in a P2P networking environment for the distribution of multimedia contents, such as bulk files, live or on-demand audio or video, etc.
The points below may reflect the hindsight gained from the disclosed inventions and/or from the inventive process, and are NOT admitted to be prior art.
Peer-to-Peer architectures leverage the end terminals to cooperatively disseminate the information instead of relying on any central entities. This approach provides the system with theoretically infinite scalability at virtually no additional cost, and therefore has ignited an explosive growth of large scale Internet services, for instance, KaZaA for file sharing, BT for bulk content distribution and PPlive for live media streaming.
FIG. 10 shows an example of the general architecture of peer-to-peer streaming systems. The original uncompressed video content is generated by the A/V source and injected into the media server. In the media server, the video content is first compressed with the playout rate to be r kbps and then is distributed to users in the peer-to-peer network through multiple video streams. In the peer-to-peer network, the video streams are forwarded among connected nodes, and at each node the downloading video content is simultaneously played by the local media player at the playout rate of r kbps.
An appealing feature of the peer-to-peer networking is that since each participating node contributes its bandwidth to the system to assist uploading, the system can self-scale to support a huge number of users online simultaneously, even for bandwidth consuming media streaming applications. Notice that all these attractive services are bandwidth intensive and normally require stringent QoS requirements. On the other hand, with millions of heterogeneous participants all over the world, organizing the network efficiently to boost the system performance with high service quality is a very difficult problem. Facing these difficulties, traditional approaches for live media streaming can mainly be grouped into three categories based on the involvement of (1) a multicast tree, (2) plural multicast trees, or (3) no tree.
The first category is to build a multicast tree across the network. Video contents are disseminated from the root and passed along the tree from parents to children. Without considering the dynamic behavior of peers, this mechanism is superior with its ease to manage. Optimization can also be easily performed within the tree by intelligently shifting among parents and their children. However, with the intense churnung of ad hoc peers, the cost of tree topology maintenance is high. Further, due to peer departures, the system often needs frequent repairs. Therefore participants will inevitably encounter turbulent QoS with large video quality fluctuation during the repairing phase. Examples of such systems include Narada and Yoid.
To enhance the robustness of the system and allow the clients to enjoy high quality services such as smooth playing of videos, the second category improves the first category by building several multicast trees simultaneously with each tree streaming one strip of the content rooted from a source. Such mechanism often employs advanced coding schemes, e.g., Multiple Description Coding or Fountain Codes, so that by downloading several streams simultaneously from different trees, the participants are able to achieve better video quality and can also tolerate the departures of partial predecessors as long as it can download at least one stream continuously. Such mechanism has been adopted in CoopNet, SplitStream and Bullet.
In the third category, there are no more tree(s) to be maintained. Instead a data-oriented approach chops the original contents into blocks of equal size and disseminates to peers disjointedly. After downloading each block in its entirety, peers can then serve it to other siblings to enhance the system service capacity. In such a scenario, in order to learn the block propagation to chase needed blocks, each peer needs to collect the block information of certain amount of peers periodically and react against the run up of fresh blocks or other accidents such as neighbor departures, heavy congestion, etc. With the unceasingly active local modifications, the network commotion will only affect several block sessions of a peer normally, and therefore the system is more robust than that of the previous tree(s) structure. For this reason, the data driven approach is widely employed in practice, for instance BT, CoolStream and PPlive. However, such mechanism makes the network even more turbulent and difficult to optimize.
With the great success of PPlive and CoolStream, large scale live streaming service has already been relatively mature. However, the term “streaming” is in fact used loosely and inaccurately. There are no general principles to guide designers seeking for an optimal system. Large scale Video-on-Demand (VoD) service, with more stringent QoS requirements and less available cooperation among peers, is far from satisfactory and still under serious research without any real systems implemented.
The rapid development of broadband residential networks has further heated up interest in large scale high quality video delivery service over the Internet. The great commercial opportunities for Internet video service have resulted in a rapid growth in the demand for a reliable live video streaming system with high quality of service (QoS) guarantee. With the failure of IP multicast, the peer-to-peer (P2P) video streaming has recently emerged as a promising and effective alternative approach. Many P2P live video streaming systems have been proposed, notably vPPLive, CoolStreaming, and End System Multicast.
One of the promising P2P multicast schemes for live video streaming applications is tree-based multicasting. Tree based P2P networks provide relatively static video delivery paths, so that the video distribution is very efficient. In tree-based P2P networks, one approach to deliver the video data is by forming a single multicast tree in the overlay with video stream delivered from the root to peers using one-way communication. However, the present inventors have realized that, due to the hierarchical structure of the tree-based P2P networks, single tree video streaming approaches have two major problems: (1) inefficient usage of leaf nodes' uploading bandwidth; and (2) sensitive to node departures. The reason behind these problems is that the forwarding of the video stream is carried out by a small subset of peers which act as interior nodes in the tree.
One effort, SplitStream, introduces a very powerful multi-tree structure, named Interior-Node-Disjoint (IND) multi-tree, to recycle the uploading bandwidth of leaf nodes and improve the robustness. The key idea of SplitStream is that every peer in the network takes part in the forwarding of the video streams by serving as an interior node in one tree of the multi-tree structure. However, SplitStream does not solve the bottleneck problem caused by the heterogeneous bandwidth of peers in multitree P2P networks, a problem also referred to as capacity aware topology formation problem. The few proposed solutions focus on how to achieve a predefined target workload for each peer in terms of number of child nodes. However, they failed to address how to determine the optimal target workload.